/**
 * @author heguochang
 * @version Id: Exercise2.java, v 0.1 2021/10/18 上午12:17 heguochang Exp $$
 */
public class Exercise4 {

    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }


    // 素数,非素数做出标记
    public static int eratosthenes(int n) {
        // false代表素数
        boolean[] isPrime = new boolean[n];
        int count = 0;

        for (int i = 2; i < n; i++) {

            // 如果是素数,则算出合数组合
            if (!isPrime[i]) {
                count++;

                // j就是合数的标记位,合数的倍数也是合数,j+=i相当于改变了2*i的系数,例如:2*i,2*i+i=3*i,3*i+i=4*i
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
}